package Intermediate_algorithm.Backtracking;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
括号生成
数字 n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]

提示：
1 <= n <= 8
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xv33m7/
 */
public class _02括号生成 {

    @Test
    public void test() {
        System.out.println(generateParenthesis(3));
    }

    //WA 不是所有可能 例如：(())(()) 不存在
    public List<String> generateParenthesis(int n) {
        List<String> res = new LinkedList<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer("()");
        if (n == 1){
            res.add(queue.poll());
            return res;
        }
        for (int i = 1; i < n; i++) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                String poll = queue.poll();
                String s1 = poll + "()";
                String s2 = "()" + poll;
                String s3 = "(" + poll + ")";
                if (!queue.contains(s1)){
                    queue.offer(s1);
                }
                if (!queue.contains(s2)){
                    queue.offer(s2);
                }
                if (!queue.contains(s3)){
                    queue.offer(s3);
                }
            }
        }
        while (!queue.isEmpty()){
            res.add(queue.poll());
        }
        return res;
    }

    //官解:方法二：回溯法
    /*
    思路和算法
    方法一还有改进的余地：我们可以只在序列仍然保持有效时才添加 ‘(’ 或 ‘)’，而不是像 方法一 那样每次添加。
    我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，
    如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/generate-parentheses/solutions/192912/gua-hao-sheng-cheng-by-leetcode-solution/
     */
    class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> ans = new ArrayList<String>();
            backtrack(ans, new StringBuilder(), 0, 0, n);
            return ans;
        }

        public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
            if (cur.length() == max * 2) {
                ans.add(cur.toString());
                return;
            }
            if (open < max) {
                cur.append('(');
                backtrack(ans, cur, open + 1, close, max);
                cur.deleteCharAt(cur.length() - 1);
            }
            if (close < open) {
                cur.append(')');
                backtrack(ans, cur, open, close + 1, max);
                cur.deleteCharAt(cur.length() - 1);
            }
        }
    }



}
